#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../include/swap.h"

using namespace std;

// 冒泡排序(从小到大)
// 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
// 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
// 3.针对新的元素重新排序，每次都会减少一个最后的元素，因为最后的元素必然是最大的，直到排序完成。
// 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 冒泡排序优化
// 1.对于n个数字排序，只需要n-1次循环，最后一次循环没有必要。
// 2.如果某次循环没有发生交换，说明已经排序完成，不需要再继续循环。

// 时间和空间复杂度
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 最优时间复杂度：O(n)  已经是排好序的，遍历一遍
void bubbleSort(int arr[], int len) {
    // for (int i = 0; i < len - 1; i++)
    // {
    //     int flag = false;
    //     for (int j = 0; j < len -1 - i; j++)
    //     {
    //         if (arr[j] > arr[j+1])
    //         {
    //             flag = true;
    //             swap(arr[j], arr[j+1]);
    //         }
    //     }
    //     // 如果某次循环没有发生交换，说明已经排序完成，不需要再继续循环
    //     if (!flag)
    //         break;
    // }

    // 更便于理解，i 是需要排序的元素个数，每一轮都会减少一个元素，因为最后一个元素必然是当前最大的元素
    for (int i = len -1; i >= 0; i--)
    {
        int flag = false;
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j+1])
            {
                flag = true;
                swap(arr[j], arr[j+1]);
            }
        }
        // 如果某次循环没有发生交换，说明已经排序完成，不需要再继续循环
        if (!flag)
            break;
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     bubbleSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }